\documentclass[11pt,letterpaper]{article}

\newcommand{\mytitle}{CS255 Homework 2}
\newcommand{\myauthor}{Kevin Lewi}
\date{February 17, 2012}

\usepackage{hwformat}

\begin{document}

\maketitle

\section*{Problem 1}

\subsection*{(a)}

A collision for the hash function means that there exist messages $m_1$ and 
$m_2$ such that $m_1 \neq m_2$ but $h(m_1) = h(m_2)$. Consider the Merkle tree, 
call it $T$, and call each block in the tree a node. We claim that there exists 
some node $v$ such that the output of $v$ under $m_1$ is equal to the output of 
$v$ under $m_2$, but the inputs to $v$ differ between $m_1$ and $m_2$. Assume 
for the sake of contradiction that this claim is false --- then, for every node 
$u$ in $T$, we would have that either $u$ has the same inputs across $m_1$ and 
$m_2$ and thus produces the same output, or $u$ has different inputs across 
$m_1$ and $m_2$ and produces a different output under $m_1$ than under $m_2$. 
However, note that the final output must be the same under $m_1$ and $m_2$, yet 
the original input must be different, since $m_1 \neq m_2$. This contradiction 
establishes the claim.

Now, look at $v$: since its inputs are different yet its output is the same 
across $m_1$ and $m_2$, then we have derived a collision for the compression 
function $f$.

\subsection*{(b)}

Let $m_1$ be a message that uses $16$ blocks, and let $m_2$ be the resulting 
input after the Merkle hash tree right before the final call to $f$ (so, $c_1$ 
is about to be combined with the message-length block). Since the message-length 
block is always set to $0$, note that $m_1$ and $m_2$ are two different strings 
(of different lengths, anyway), and yet they hash to the same value. This is a 
collision.

\section*{Problem 2}

Fix two arbitrary messages $u$ and $v$, first ($u \neq v$). To show that $f_1$ 
does not work, consider $a = D(v, u \oplus v)$, $c = D(u \oplus v, v)$, and $d = 
u \oplus v$. Then, note that $f_1(a,v) = E(v, D(v, u \oplus v)) \oplus v) = u$. 
Also, $u = E(u \oplus v, D(u \oplus v, v)) \oplus u \oplus v = f_1(c,d)$. 
Therefore, we've shown that $f_1(a,v) = f_1(c,d)$, and, as long as we choose $u$ 
and $v$ such that $d \neq u$ and $d \neq v$, we have a collision.

For $f_2$ not working, we also fix an arbitrary message $w$ that is not $u$ nor 
$v$. We will soon choose a message $z$ to make things work. But first, consider 
$f_2(u,z) = E(u,u) \oplus z$. Since we can choose $z$ arbitrarily, we would like 
to make it such that $E(u,u) \oplus z = E(v,v) \oplus w$. Choose $z$ such that 
that is true, and then we have, since $E(v,v) \oplus w = f_2(v,w)$, that 
$f_1(u,z) = f_2(v,w)$, which is a collision.

\section*{Problem 3}

Let $m_1$ be the all-ones string, suppose it has $b$ blocks, and compute $H(m)$. 
Now, given $H(m)$, set $z = D(k, D(k, D(k, \cdots, D(k, H(m)))))$, where we run 
exactly $b$ successive decryptions. Then, set $m_2$ to be $z$ for the first 
block, and then all zeros for all of the remaining $b-1$ blocks. Then, $m_1 \neq 
m_2$ yet $H(m_1) = H(m_2)$.

\section*{Problem 4}

\subsection*{(a)}

A user $B_i$ can send a message to a user $B_j$ and it would look the same as if 
$A$ sent it, since everyone uses the same secret key $k$.

\subsection*{(b)}

The sets $S_1, \cdots, S_n$ should form an antichain over the power set, under 
set inclusion. So, there does not exist an $S_i$ and $S_j$ such that $S_i 
\subseteq S_j$.

\subsection*{(c)}

Consider all $\binom{5}{2} = 10$ possible size-$2$ subsets of the set of $5$
keys. These will be the sets $S_1, \cdots, S_{10}$, and of course no set 
includes another since they all have size $2$ and none are identical.

\section*{Problem 5}

I don't know

\section*{Problem 6}

\subsection*{(a)}

Let $z = y^{(p-1)/2} \pmod{p}$. The claim is that $z=1$ iff $x$ is even. To see 
this, note that if $z = 1$, then $y$ is a quadratic residue, as $z^2 = y$. 
Therefore, $x$ has to be even. Conversely, if $x$ is even, then $y$ is a 
quadratic residue. Then, by Euler's formula, $z = 1$.

\subsection*{(b)}

Given that $x$ is even, we can just do the same procedure but this time look at 
$g^{x/2}$ and $y^{((p-1)/2)/2} = y^{(p-1)/4)} \pmod{p}$, as the same rules about 
quadratic residues apply.

\subsection*{(c)}

We already have dealt with the case when $x$ is even. As we are determining the 
bits of $x$, we can set the LSB of $x$ to be $0$ when we determine it is even, 
and this procedure can be repeated by stripping off a factor of $2$ and 
repeating. The only issue we have not dealt with yet is when $x$ is odd. But 
this is actually quite easy to deal with. When we determine that $x$ is odd, 
instead of considering $y = g^{x/2}$ in the next iteration, consider $y = 
g^{x-1}$. So, we just keep repeating this procedure, and eventually we will have 
recovered every bit of $x$.

\subsection*{(d)}

We can't do the operation of taking the exponent of $y$ by $(p-1)/2$ if $p$ is 
not of the form $2^k+1$.

\section*{Problem 7}

\subsection*{(a)}

Party $i$ can compute the multiplicative inverse of $a_i \pmod{q}$, denote this 
as $w_i$. Then, taking $z_i^{w_i} = g^{a_i \cdot b \cdot w_i} = g^b = y$.

\subsection*{(b)}

$y$ is not computable by an eavesdropper since only $g^a$ and $g^{ab}$ are sent, 
and it is not possible to determine $g^b$ under the Diffie-Hellman assumption.

\subsection*{(c)}

\end{document}
